package Algorithm.PriorityQueue;

import java.util.PriorityQueue;
//https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/submissions/
public class Leetcode786 {
    class Solution {
        public int[] kthSmallestPrimeFraction(int[] arr, int k) {
            // 判断 a/b 与 c/d 的大小时，可以使用 a*d 与 c*b 的大小来判断
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((x,y)->{return arr[x[0]]*arr[y[1]]-arr[y[0]]*arr[x[1]];});
            // PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((x,y)->{return arr[y[0]]*arr[y[1]]- arr[x[0]]*arr[x[1]];});


            for (int i=1;i<arr.length;i++){
                priorityQueue.add(new int[]{0,i});
            }

            int[] temp = null;
            for (int i=0;i<k;i++){
                temp = priorityQueue.poll();
                // System.out.println(temp[0]+" "+temp[1]);
                if(temp[0]<temp[1]){
                    priorityQueue.offer(new int[]{temp[0]+1,temp[1]});
                }
            }

            return new int[]{arr[temp[0]],arr[temp[1]]};
        }
    }
}
